package LeetcodeTest_twenty;
//338.比特位计数
import java.util.ArrayList;

public class countBits
{
    public static void main(String[] args)
    {
        int nums[]=new int[6];
        nums=solution.countBits(5);
        for(int i=0;i<nums.length;i++)
            System.out.println(nums[i]);
    }
}
class solution
{
    public static int[] countBits(int num)
    {
        int i,j;
        int n;
        int countBit[]=new int[num+1];
        ArrayList<Integer> power=new ArrayList<Integer>();
        for(i=0;i<=num;i++)
        {
            if(i==0||i==1)
                countBit[i]=i;
            if(countBit[i]==1)
                power.add(i);
            n=i;
            if(i>=2)
            {
                j=power.size()-1;
                if(n%power.get(j)==0)
                {
                    countBit[i] = 1;
                    power.add(i);
                }
                else
                {
                    while (j >= 0)
                    {
                        countBit[i] = countBit[i] + n / power.get(j);
                        n = n % power.get(j);
                        j--;
                    }
                }
            }
        }
        return countBit;
    }
}